package top.drose;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class P46_1 {
    //这里是比较自己的bin_search和lower_bound的正确性
    //因为java中没有lower_bound所以这里实现
    public static void main(String[] args) {


    }

    // 实现类似于 lower_bound 的功能
    // 这里实现了重载
    public static int lowerBound(List<Integer> list, int target) {
        int index = Collections.binarySearch(list, target);
        if (index < 0) {
            index = -index - 1;
        }
        return index;
    }


//    如果 target 存在于数组中：
//
//    Arrays.binarySearch 返回的 index 是 target 在数组中的索引（index >= 0）。
//
//    直接返回这个 index。
//
//    如果 target 不存在于数组中：
//
//    Arrays.binarySearch 返回的 index 是负数（index < 0）。
//
//    通过 index = -index - 1 计算出 insertion point，即第一个大于 target 的元素的索引。
//
//    返回这个 insertion point。
    public static int lowerBound(int[] array, int target) {
        //通过自带的功能找index，如果找不到

        int index = Arrays.binarySearch(array, target);
        if (index < 0) {
            index = -index - 1;
        }
        return index;
    }

}
